package leetcode_1000;

/**
 *@author 周杨
 *KnightDialer_935 一个皇后在棋盘上走 每次走代表一个手机里的数字 问走N步 能有多少种结果 
 *describe:用动态规划 AC 94%
 *2018年11月21日 上午10:44:32
 */
public class KnightDialer_935 {
	public int knightDialer(int N) {
		if(N==1)
        	return 10;
        final int MOD=1000000007;
        long[]dp=new long[] {1,1,1,1,1,0,1,1,1,1};
        int now=1;
        while(now++!=N) {
        	long temp[]=new long[10];
        	temp[0]=dp[4]+dp[6];
        	temp[1]=dp[8]+dp[6];
        	temp[2]=dp[7]+dp[9];
        	temp[3]=dp[4]+dp[8];
        	temp[4]=dp[3]+dp[9]+dp[0];
        	temp[6]=dp[0]+dp[1]+dp[7];
        	temp[7]=dp[6]+dp[2];
        	temp[8]=dp[1]+dp[3];
        	temp[9]=dp[2]+dp[4];
        	for(int i=0;i<=9;++i) {
        		dp[i]=(temp[i]+MOD)%MOD;
        	}
        }
        long res=0;
        for(long i:dp) {
        	res=(res+i+MOD)%MOD;
        }
        return (int) res;
    }
}
